package alo;

/**
 * @ClassName t7
 * @Description 返回第K大的数
 * @Author Fanxc
 * @DATE 2021/4/20 15:57
 * @Version 1.0
 */
public class t7 {
    public int findKth(int[] a, int n, int K) {
        int i=0;
        int j=n-1;
        //第K大就是第n-K+1小（比如3个数，第2大就是第3-2+1=2小）
        //因为快排是顺序排列的，当然修改partition中左边为大于枢纽也是可以的
        K=n-K+1;
        while (i<=j){
            int p=partition(a,i,j);
            if (p==K-1){
                return a[p];
            }else if (p>K){
                j=p;
            }else {
                i=p+1;
            }
        }
        return -1;
    }
    int partition(int[] A,int low,int high) {
        int left,right,temp,pivot_item=A[low];
        left=low;
        right=high;
        while (left<right){
            while (A[left]<=pivot_item&&left<high){//需要时刻注意left<high，防止数组越界
                left++;
            }
            while (A[right]>pivot_item&&right>low){//与上边同理
                right--;
            }
            if (left<right){
                temp=A[left];
                A[left]=A[right];
                A[right]=temp;
            }
        }
        A[low]=A[right];
        A[right]=pivot_item;
        return right;
    }
}
